SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

</head>

</header>

</div>

Le code de Gray, également appelé code Gray, code de Gros-Gray, ou code binaire réfléchi, est un type de <a href="Syst%C3%A8me_binaire" title="Système binaire">codage binaire</a> permettant de ne modifier qu'un seul bit à la fois quand un nombre est augmenté d'une unité. Cette propriété est importante pour plusieurs applications.

Le code porte les noms d'Agathon-Louis Gros qui publia un article sur le sujet en 1872<a href="#cite_note-1">[1]</a>,<a href="#cite_note-2">[2]</a>,<a href="#cite_note-:02-3">[3]</a> et de l'ingénieur américain <a href="Frank_Gray_(physicien_et_chercheur)" title="Frank Gray (physicien et chercheur)">Frank Gray</a> qui déposa un brevet sur ce code en 1947<a href="#cite_note-:0-4">[4]</a>.

<div class="mw-heading mw-heading2"><h2 id="Principe_et_exemple">Principe et exemple</h2></div>

Le code de Gray est un codage binaire, c'est-à-dire une fonction qui associe à chaque nombre une représentation binaire. Cette méthode est différente du codage binaire naturel. Le tableau suivant montre partiellement le codage sur 4 bits (seules les 8 premières valeurs sont présentées, les huit suivantes avec le premier bit à 1 n'y sont pas).

<th scope="col">Codage décimal

</th>

<th scope="col">Codage binaire naturel

</th>

<th scope="col">Codage Gray ou binaire réfléchi

</th></tr>

<tr>

<td>0000

</td></tr>

<tr>

<td>0001

</td></tr>

<tr>

<td>0011

</td></tr>

<tr>

<td>0010

</td></tr>

<tr>

<td>0110

</td></tr>

<tr>

<td>0111

</td></tr>

<tr>

<td>0101

</td></tr>

<tr>

<td>0100

</td></tr></tbody></table>

La différence principale entre les deux est le fait que le codage de Gray de deux nombres consécutifs ne diffère que d'une position. Par exemple 5 est codé par 0111, et 6 est codé par 0101 : ici seul le deuxième bit change.

<div class="mw-heading mw-heading2"><h2 id="Construction_de_la_table_par_symétrie">Construction de la table par symétrie</h2></div>

Le nom de code binaire réfléchi, comme autre nom du code de Gray, vient d'une méthode de construction basée sur la réflexion de blocs de codes déjà construits :

<ul><li>on choisit un code de départ : zéro est codé 0 et un est codé 1,</li>

<li>puis, à chaque fois qu'on a besoin d'un bit supplémentaire, on symétrise la liste des codes déjà obtenus (comme une réflexion dans un miroir),</li>

<li>enfin, on rajoute un 0 puis un 1 au début (à gauche) de chacun des codes. On a ainsi doublé le nombre de codes formés.</li></ul>

Exemple :

<pre>0 0 0 .0 0 00 0 .00 0 000

1 1 1 .1 1 01 1 .01 1 001

miroir→------ 2 .11 2 011

2 .1 2 11 3 .10 3 010

3 .0 3 10 -------

4 .10 4 110

5 .11 5 111

6 .01 6 101

7 .00 7 100

</pre>

<div class="mw-heading mw-heading2"><h2 id="Méthodes_d'incrémentation">Méthodes d'incrémentation</h2></div>

Il existe plusieurs méthodes pour incrémenter un nombre écrit selon le code de Gray (c'est-à-dire lui ajouter 1).

<div class="mw-heading mw-heading3"><h3 id="Inverser_pour_obtenir_un_nouveau_nombre">Inverser pour obtenir un nouveau nombre</h3></div>

Pour passer d'une ligne à la suivante, on inverse le bit le plus à droite possible conduisant à un nombre nouveau. Cette méthode présente l'inconvénient de devoir connaître tous les codes de Gray qui précèdent.

<div class="mw-heading mw-heading3"><h3 id="Selon_la_parité">Selon la parité</h3></div>

Une autre méthode de calcul permettant de passer d'un nombre de Gray au suivant, et qui présente l'avantage de ne pas nécessiter de connaître l'ensemble des nombres précédents est la suivante<a href="#cite_note-5">[5]</a> :

<ul><li>si le nombre de 1 est pair, il faut inverser le dernier chiffre.</li>

<li>si le nombre de 1 est impair, il faut inverser le chiffre situé à gauche du 1 le plus à droite.</li></ul>

<caption>Exemple d'incrément basé sur la parité

</caption>

<td style="border-style:hidden solid;border-left-style:hidden"> 44 (pair)

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden"> 27 (impair)

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<td style="border-style:hidden solid;border-left-style:hidden">dernier chiffre</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden">chiffre avant le dernier 1</td>

<td>←

</td>

<td style="border-style:hidden solid;border-left-style:hidden">.

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden">44 → 45

</td>

<td>0

</td>

<td>1

</td>

<td>1

</td>

<td>1

</td>

<td>0

</td>

<td>1

</td>

<td>1

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden">27 → 28

</td>

<td>0

</td>

<td>1

</td>

<td>0

</td>

<td style="background:#FF0;color:#222">0

</td>

<td>1

</td>

<td>0

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Calcul_de_moitié_et_double">Calcul de moitié et double</h2></div>

Une méthode de calcul de la moitié d'un nombre pair consiste à éliminer le dernier chiffre et donc décaler les autres chiffres d'une position à droite.

<caption>Exemple de calcul de la moitié

</caption>

<td style="border-style:hidden solid;border-left-style:hidden"> 44

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden">22

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden">44 → 22

</td>

<td>

</td>

<td>0

</td>

<td>1

</td>

<td>1

</td>

<td>1

</td>

<td>0

</td>

<td>1

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden">22 → 11

</td>

<td>

</td>

<td>0

</td>

<td>1

</td>

<td>1

</td>

<td>1

</td>

<td>0

</td></tr></tbody></table>

Une méthode de calcul du double d'un nombre consiste à insérer un chiffre supplémentaire à droite et donc décaler les autres chiffres d'une position à gauche.

<ul><li>si le nombre de chiffres 1 est pair, le nombre est pair, il faut insérer un zéro à droite</li>

<li>si le nombre de chiffres 1 est impair, le nombre est impair, il faut insérer le chiffre 1 à droite</li></ul>

<caption>Exemple de calcul du double

</caption>

<td style="border-style:hidden solid;border-left-style:hidden">22 (pair)

</td>

<td>

</td>

<td>0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden">11 (impair)

</td>

<td>

</td>

<td>0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td>0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden"> 44

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

</td>

<td style="border-style:hidden solid;border-left-style:hidden"> 22

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FF0;color:#222">1

</td>

<td style="background:#0FF;color:#222">1

</td>

<td style="background:#FFF;color:#222">0

</td>

<td style="background:#FF0;color:#222">1

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Intérêt_:_Éviter_des_états_transitoires">Intérêt : Éviter des états transitoires</h2></div>

Le fait de modifier plusieurs bits lors d'une simple <a href="Incr%C3%A9mentation" title="Incrémentation">incrémentation</a> peut mener, selon le circuit logique, à un <a href="%C3%89tat_transitoire" title="État transitoire">état transitoire</a> indésirable dû au fait que le chemin logique de chaque bit dispose d'un délai différent. Ainsi, lors du passage de la valeur "01" à la valeur "10" en <a href="Syst%C3%A8me_binaire" title="Système binaire">binaire naturel</a>, il est possible d'observer un état transitoire "00" si le bit de droite commute en premier ou "11" dans le cas contraire. Si le circuit dépendant de cette donnée n'est pas <a href="Circuit_synchrone" title="Circuit synchrone">synchrone</a>, l'état transitoire peut perturber les opérations en faisant croire au système qu'il est passé par un état normalement non atteint à ce stade. Cela apparait pour les capteurs de positions, par exemple sur des règles optiques. Ce code permet de contourner cet aléa en forçant la commutation d'un seul bit à la fois, évitant ainsi les états transitoires.

<caption>Intérêt du code de gray

</caption>

</td>

<th>Transitions incertaines sans code de Gray

</th>

<th>Transitions déterministes avec le code de Gray

</th></tr>

<tr>

<th>Modèle théorique (en haut) Réalité physique (en bas)

</th>

<td>

</td>

<td>

</td></tr>

<tr>

</td>

<td>Sans code de gray deux transitions peuvent se produire au lieu d'une. Entre ces deux transition l'état intermédiaire est indéterminé et indéterminable. C'est par exemple le cas entre les transitions t1 et t2 ou entre t3 et t4.

</td>

<td>Avec le code de gray deux transitions ne peuvent se produire au lieu d'une.

Autour de t1, il n'y a pas de changement. t1 n'est pas une transition.

La transition survient sur t2.

Autour de t4, il n'y a pas de changement. t4 n'est pas une transition.

La transition survient sur t3.

</td></tr></tbody></table>

<caption>Unicité des transitions

</caption>

<td style="border-style:hidden solid;border-left-style:hidden"> 1 :

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden"> 2 :

</td>

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden"> 3 :

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

</td>

</td>

<td style="border-style:hidden solid;color:#801">⬌

</td>

</td>

</td>

</td>

<td style="background:#FFF;color:#222">0

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Roue_codeuse">Roue codeuse</h3></div>

Le code de gray trouve une application pratique dans la <a href="Roue_codeuse" title="Roue codeuse">roue codeuse</a>. Dans l'illustration, on trouve huit états et huit transitions sans qu'il n'y ait ni maximum, ni minimum, du fait des symétries.

Chaque huitième de tour n'occasionne qu'une unique transition. Ceci permet donc bien d'encoder un angle.

L'illustration montre la forme de la roue, la table montre les transitions entre états, le graphe montre la position les transitions sur la roue. Le code est implémenté en noir et blanc, pour explication, les transitions sont explicitées en rouge, vert et bleu.

Ces explications prennent comme références les directions d'une girouette (E=est, N=nord, O=ouest, S=sud).

<th>Transition

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td></tr>

<tr>

<th>Cercle extérieur

</th>

</td>

</td>

<td colspan="3" style="background: white; color: black;">Ouest</td>

</td>

</td>

</td>

<td colspan="2" style="background: black; color: white;">Nord

</td></tr>

<tr>

<th>Cercle médian

</th>

<td style="background: blue; color: black;">N

</td>

<td colspan="7" style="background: black; color: white;">Ouest</td>

<td style="background: blue; color: black;">S

</td>

<td style="background: blue; color: black;">N

</td></tr>

<tr>

<th>Cercle intérieur

</th>

<td style="background: red; color: black;">E

</td>

<td style="background: red; color: black;">O

</td>

<td style="background: red; color: black;">E

</td>

<td colspan="7" style="background: white; color: black;">Nord

</td></tr>

<tr>

<th>Transition

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: red; color: black;">i

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: green; color: black;">e

</td>

<th style="background: gray; color: gray;">....

</th>

<td style="background: blue; color: black;">m

</td></tr></tbody></table>

/* start https://fr.wikipedia.org/ */

.mw-parser-output .mw-graph-img{width:inherit;height:inherit}

/* end https://fr.wikipedia.org/ */

</style>

<div class="mw-heading mw-heading3"><h3 id="Souris">Souris</h3></div>

Le décodage des signaux lumineux d'un axe de <a href="Souris_(informatique)#Technologie_mécanique" title="Souris (informatique)">souris mécanique</a> est un décodage de code de Gray à 2 bits (décodage différentiel dans ce cas, car ce que l'on veut obtenir n'est pas la valeur décodée mais les transitions ±1 mod 4 de la valeur décodée).

<div class="mw-heading mw-heading3"><h3 id="Tables_de_Karnaugh">Tables de Karnaugh</h3></div>

Le code Gray sert également dans les <a href="Table_de_Karnaugh" title="Table de Karnaugh">tables de Karnaugh</a> utilisées lors de la conception de circuits logiques.

<div class="mw-heading mw-heading3"><h3 id="Code_Baudot">Code Baudot</h3></div>

Le principe du code de Gray se retrouve dans le <a href="Code_Baudot" title="Code Baudot">code Baudot</a>, dans lequel les voyelles et les consonnes sont classées dans leur ordre alphabétique, et un seul bit change entre deux lettres successives.

Otto Schäffler aurait également eu un télégraphe similaire.

<pre>Let ·Fig. · V · IV· · I · II·III·

----+-----+---+---+---+---+---+---+

A · 1 · · · · ● · · ·

É / · 1/ · · · · ● · ● · ·

E · 2 · · · · · ● · ·

I · 3/ · · · · · ● · ● ·

O · 5 · · · · ● · ● · ● ·

U · 4 · · · · ● · · ● ·

Y · 3 · · · · · · ● ·

B · 8 · · ● · · · · ● ·

C · 9 · · ● · · ● · · ● ·

D · 0 · · ● · · ● · ● · ● ·

F · 5/ · · ● · · · ● · ● ·

G · 7 · · ● · · · ● · ·

H · ¹ · · ● · · ● · ● · ·

J · 6 · · ● · · ● · · ·

Fig. Bl. · · ● · · · · ·

* · * · ● · ● · · · ·

K · ( · ● · ● · · ● · ·

L · = · ● · ● · · ● · ● ·

M · ) · ● · ● · · · ● ·

N · £ · ● · ● · · · ● · ●

P · + · ● · ● · · ● · ● · ●

Q · / · ● · ● · · ● · · ●

R · – · ● · ● · · · · ●

S · 7/ · ● · · · · · ●

T · ² · ● · · · ● · · ●

V · ¹ · ● · · · ● · ● · ●

W ·  ? · ● · · · · ● · ●

X · 9/ · ● · · · · ● ·

Z ·  : · ● · · · ● · ● ·

– · . · ● · · · ● · ·

Let. Bl. · ● · · · · · ·

</pre>

<div class="mw-heading mw-heading2"><h2 id="Transcodage_binaire">Transcodage binaire</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Transcodage_binaire_/_Gray">Transcodage binaire / Gray</h3></div>

En notant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=b_{0}b_{1}...b_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=b_{0}b_{1}...b_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de9d4c8f3298f0e7ab83b44c958ee20ffb274293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.388ex; height:2.509ex;" alt="{\displaystyle b=b_{0}b_{1}...b_{k}}" loading="lazy"> un entier écrit en binaire (où <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e425056f502ca07b103ffbf6ac4720e0f8a01f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.052ex; height:2.509ex;" alt="{\displaystyle b_{0}}" loading="lazy"> est le <a href="Bit_de_poids_fort" title="Bit de poids fort">bit de poids fort</a>), et de même en notant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g=g_{0}g_{1}...g_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g=g_{0}g_{1}...g_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1be2a1c1359a456962b24c575b7b4e0190786c68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.841ex; height:2.009ex;" alt="{\displaystyle g=g_{0}g_{1}...g_{k}}" loading="lazy"> le code de Gray correspondant, il est possible de montrer (par exemple en utilisant les tables de Karnaugh), que

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{i}=b_{i}\oplus b_{i-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9f3791eda9dea50a0a8f26e4bfef55580bb444e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.543ex; height:2.509ex;" alt="{\displaystyle g_{i}=b_{i}\oplus b_{i-1}}" loading="lazy"> (où <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> désigne la fonction <a href="OU_exclusif" class="mw-redirect" title="OU exclusif">OU exclusif</a>) ; autrement dit, pour obtenir <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">, il suffit d'effectuer un OU exclusif entre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> et ce même nombre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> décalé d'un bit vers la droite (c'est-à-dire, en binaire, divisé par 2), ce qu'exprime la fonction suivante écrite en <a href="Langage_C" class="mw-redirect" title="Langage C">langage C</a> :

Algorithme de codage d'un nombre b en code de Gray :

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> g = b ^ (b >> 1)

</pre></div>

Par exemple, le <a href="Nombre_d%C3%A9cimal" title="Nombre décimal">nombre décimal</a> 7 s'écrit 0111 en base 2. Son code de Gray s'obtient comme suit :

<pre> 0111

^ 0011

------

0100

</pre>

7 est représenté par 0100 en code de Gray.

Algorithme de décodage rapide pour des mots de 64 bits (pour des mots de 32 bits, remplacer 32 par 16) :

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> long grayInverse(long n) {

long ish, ans, idiv;

ish = 1;

ans = n;

while(1) {

idiv = ans >> ish;

ans ^= idiv;

if (idiv <= 1 || ish == 32)

return ans;

ish <<= 1; // double le nb de shifts la prochaine fois

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Transcodage_Gray_/_binaire">Transcodage Gray / binaire</h3></div>

En notant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=b_{0}b_{1}...b_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=b_{0}b_{1}...b_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/de9d4c8f3298f0e7ab83b44c958ee20ffb274293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.388ex; height:2.509ex;" alt="{\displaystyle b=b_{0}b_{1}...b_{k}}" loading="lazy"> un entier écrit en binaire (où <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9e425056f502ca07b103ffbf6ac4720e0f8a01f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.052ex; height:2.509ex;" alt="{\displaystyle b_{0}}" loading="lazy"> est le <a href="Bit_de_poids_fort" title="Bit de poids fort">bit de poids fort</a>), et de même en notant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g=g_{0}g_{1}...g_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g=g_{0}g_{1}...g_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1be2a1c1359a456962b24c575b7b4e0190786c68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.841ex; height:2.009ex;" alt="{\displaystyle g=g_{0}g_{1}...g_{k}}" loading="lazy"> le code de Gray correspondant, selon ce qui précède, on détermine facilement le nombre binaire d'un code de Gray donné : <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}=g_{0}\oplus g_{1}\oplus g_{2}\oplus ...\oplus g_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}=g_{0}\oplus g_{1}\oplus g_{2}\oplus ...\oplus g_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/078d0a644990e280269341262baef46f81b5a385.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.693ex; height:2.509ex;" alt="{\displaystyle b_{i}=g_{0}\oplus g_{1}\oplus g_{2}\oplus ...\oplus g_{i}}" loading="lazy"> (où <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \oplus }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8b16e2bdaefee9eed86d866e6eba3ac47c710f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" loading="lazy"> désigne la fonction <a href="OU_exclusif" class="mw-redirect" title="OU exclusif">OU exclusif</a>).

On a donc :

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{0}=g_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6133f7bba78458fab1f9445bba9630767bd273b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.314ex; height:2.509ex;" alt="{\displaystyle b_{0}=g_{0}}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{1}=g_{0}\oplus g_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4225a545908b1957f1f9206a3c236b7c04e0a018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.317ex; height:2.509ex;" alt="{\displaystyle b_{1}=g_{0}\oplus g_{1}}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{2}=g_{0}\oplus g_{1}\oplus g_{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f23903b27060c11e238c825308a084172dceb4d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.321ex; height:2.509ex;" alt="{\displaystyle b_{2}=g_{0}\oplus g_{1}\oplus g_{2}}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{3}=g_{0}\oplus g_{1}\oplus g_{2}\oplus g_{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/009cae6d507e18ef676ab48750c33a78c3d00155.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.325ex; height:2.509ex;" alt="{\displaystyle b_{3}=g_{0}\oplus g_{1}\oplus g_{2}\oplus g_{3}}" loading="lazy">

etc.

Donc pour obtenir le code binaire d'un code de Gray donné, on passe de gauche (poids fort) à droite (poids faible). Le bit de poids fort est le même en binaire que dans le code de Gray <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{0}=g_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{0}=g_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6133f7bba78458fab1f9445bba9630767bd273b3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.314ex; height:2.509ex;" alt="{\displaystyle b_{0}=g_{0}}" loading="lazy">. Le bit binaire suivant reste le même si le bit de Gray suivant vaut zéro et change si le bit de Gray suivant vaut 1. On répète cela pour tous les bits, jusqu'au bit de poids le plus faible.

<div class="mw-heading mw-heading2"><h2 id="Historique">Historique</h2></div>

L'ingénieur américain <a href="Frank_Gray_(physicien_et_chercheur)" title="Frank Gray (physicien et chercheur)">Frank Gray</a> déposa un brevet sur ce code en 1947<a href="#cite_note-:0-4">[4]</a>, mais le code est plus ancien ; il a notamment été utilisé dans le code Baudot.

Luc-Agathon-Louis Gros, qui fut <a href="Clerc_de_notaire" title="Clerc de notaire">clerc de notaire</a> puis conseiller à la Cour d'appel de <a href="Lyon" title="Lyon">Lyon</a>, publia en 1872 un opuscule, Théorie du baguenodier par un clerc de notaire lyonnais, où ce code était présenté pour la première fois en lien avec un casse-tête, le <a href="Jeu_du_baguenaudier" title="Jeu du baguenaudier">jeu du baguenaudier</a><a href="#cite_note-6">[6]</a>.

Cette séquence a été notamment vulgarisée dans le jeu du baguenaudier<a href="#cite_note-7">[7]</a> (jeu qui nous a été transmis par <a href="J%C3%A9r%C3%B4me_Cardan" title="Jérôme Cardan">Jérôme Cardan</a> et qui a été résolu par <a href="John_Wallis" title="John Wallis">John Wallis</a>).

<caption>Jeu du baguenaudier

</caption>

<td style="border-style:hidden solid;border-left-style:hidden">Case 1 :

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden">Case 2 :

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden">Case 3 :

</td>

</td>

</td>

</td>

</td>

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

</td>

</td>

<td style="background:#FFF;color:#222">0

</td></tr>

<tr>

<td style="border-style:hidden solid;border-left-style:hidden">Case 4 :

</td>

</td>

</td>

<td style="border-style:hidden solid">⬌

</td>

</td>

</td>

</td>

</td>

</td>

</td>

</td>

<td style="background:#FFF;color:#222">0

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Références">Références</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Jean-Paul Delahaye, « <cite style="font-style:normal">Voyageurs et baguenaudiers</cite> », Pour la Science, <abbr class="abbr" title="numéro">no</abbr> 238,‎ <time class="nowrap" datetime="0097-08" data-sort-value="0097-08">août 97</time> (<a rel="nofollow" class="external text" href="https://www.cristal.univ-lille.fr/profil/jdelahay/pls/044.pdf">lire en ligne</a>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Voyageurs+et+baguenaudiers&rft.jtitle=Pour+la+Science&rft.issue=238&rft.aulast=Delahaye&rft.aufirst=Jean-Paul&rft.date=Ao%C3%BBt+97&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray">

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Jean-Paul Delahaye, « <cite style="font-style:normal">Dérivées et intégrales dans le monde des 0 et des 1</cite> », Bibliothèque Tangente, <abbr class="abbr" title="numéro">no</abbr> 50,‎ <time>2014</time>, <abbr class="abbr" title="pages">p.</abbr> 106-111<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=D%C3%A9riv%C3%A9es+et+int%C3%A9grales+dans+le+monde+des+0+et+des+1&rft.jtitle=Biblioth%C3%A8que+Tangente&rft.issue=50&rft.aulast=Delahaye&rft.aufirst=Jean-Paul&rft.date=2014&rft.pages=106-111&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray">

</li>

<li id="cite_note-:02-3"><a href="#cite_ref-:02_3-0">↑</a> Jean-Paul Delahaye, « <cite style="font-style:normal">Des suites exotiques pour écrire les nombres</cite> », Pour la Science, <abbr class="abbr" title="numéro">no</abbr> 568,‎ <time class="nowrap" datetime="2025-02" data-sort-value="2025-02">février 2025</time>, <abbr class="abbr" title="pages">p.</abbr> 75-76<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Des+suites+exotiques+pour+%C3%A9crire+les+nombres&rft.jtitle=Pour+la+Science&rft.issue=568&rft.aulast=Delahaye&rft.aufirst=Jean-Paul&rft.date=2025-02&rft.pages=75-76&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray">

</li>

<li id="cite_note-:0-4"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Frank Gray pour <a href="Bell_Labs" class="mw-redirect" title="Bell Labs">Bell Labs</a>, <a rel="nofollow" class="external text" href="https://www.google.com/patents/US2632058">Brevet U.S. 2,632,058 : Pulse code communication</a>, déposé le 13 novembre 1947, publié le 17 mars 1953, sur <a href="Google_Patents" title="Google Patents">Google Patents</a>.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> M. Ziaur Rahman et J. Ian Munro, « <cite style="font-style:normal" lang="en">Integer Representation and Counting in the Bit Probe Model</cite> », Algorithms and Computation, Springer,‎ <time>2007</time>, <abbr class="abbr" title="pages">p.</abbr> 5–16 (<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> 978-3-540-77120-3, <a href="Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1007/978-3-540-77120-3_3">10.1007/978-3-540-77120-3_3</a>, <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-540-77120-3_3">lire en ligne</a>, consulté le <time class="nowrap" datetime="2025-08-27" data-sort-value="2025-08-27">27 août 2025</time>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Integer+Representation+and+Counting+in+the+Bit+Probe+Model&rft.jtitle=Algorithms+and+Computation&rft.aulast=Rahman&rft.aufirst=M.+Ziaur&rft.au=Munro%2C+J.+Ian&rft.date=2007&rft.pages=5%E2%80%9316&rft.isbn=978-3-540-77120-3&rft_id=info%3Adoi%2F10.1007%2F978-3-540-77120-3_3&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray">

</li>

<li id="cite_note-6"><a href="#cite_ref-6">↑</a> Luc-Agathon-Louis Gros, <cite class="italique">Théorie du baguenodier par un clerc de notaire lyonnais</cite>, Lyon, <a href="Aim%C3%A9_Vingtrinier" title="Aimé Vingtrinier">Aimé Vingtrinier</a>, <time>1872</time> (<a rel="nofollow" class="external text" href="https://books.google.fr/books?id=EcoBJRekd-sC&pg=PP1">lire en ligne</a>)<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Th%C3%A9orie+du+baguenodier+par+un+clerc+de+notaire+lyonnais&rft.place=Lyon&rft.pub=Aim%C3%A9+Vingtrinier&rft.aulast=Gros&rft.aufirst=Luc-Agathon-Louis&rft.date=1872&rft_id=https%3A%2F%2Fbooks.google.fr%2Fbooks%3Fid%3DEcoBJRekd-sC%26pg%3DPP1&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray">.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">↑</a> <a href="%C3%89douard_Lucas" title="Édouard Lucas">Édouard Lucas</a>, <cite class="italique">Récréations mathématiques</cite>, <abbr class="abbr" title="volume">vol.</abbr> 1, Paris, <a href="Gauthier-Villars" title="Gauthier-Villars">Gauthier-Villars</a>, <time>1882</time>, « Septième récréation : Le jeu du baguenaudier », <abbr class="abbr" title="pages">p.</abbr> 161–186<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=R%C3%A9cr%C3%A9ations+math%C3%A9matiques&rft.place=Paris&rft.pub=Gauthier-Villars&rft.aulast=Lucas&rft.aufirst=%C3%89douard&rft.date=1882&rft.volume=1&rft.pages=161%E2%80%93186&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+de+Gray"> : dans le « <a rel="nofollow" class="external text" href="https://archive.org/stream/rcrationsmathma00lucagoog#page/n215/mode/2up">Tableau des deux marches du Baguenaudier</a> », <abbr class="abbr" title="page(s)">p.</abbr> 185–186, on trouve les valeurs du code de Gray dans la colonne Baguenaudes.

</li>

</ol></div>

</div>

<ul id="bandeau-portail" class="bandeau-portail"><li> Portail des mathématiques </li> <li> Portail de l'informatique théorique </li> <li> Portail des télécommunications </li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2025-08-27" href="https://fr.wikipedia.org/wiki/?title=Code_de_Gray&oldid=228476507">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>